package org.example.sort;

import java.util.Arrays;

public class InsertSort {

    public static void main(String[] args) {
        int[] arr = {4,3,2,1};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void insertSort(int[] arr){

        for (int i=1; i<arr.length; i++){
            int insertValue = arr[i];
            int insertIndex = i - 1;
            //当数组下标不越界，每找到插入的值小于先前插入的值时，先前插入的数后移一位，
            // 插入数组下标就前移一位
            while(insertIndex >= 0 && insertValue < arr[insertIndex]){
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //找到要插入的地方时insertIndex+1后，赋值
            if (insertIndex + 1 != i){
                arr[insertIndex + 1] = insertValue;
            }
        }
    }
}
